1. Field of the Invention
The present invention relates to a 3D shape generation apparatus. More particularly, the present invention relates to a device for generating an objected captured in a camera image as a 3D shape on a display, based on camera images taken from a plurality of directions.
2. Description of the Prior Art
The increasing performance of computer systems in recent years and the progress in multimedia technology have led to a steadily improving environment for high-quality 3D computer graphics (referred to as xe2x80x9cCGxe2x80x9d in the following), even for use in personal computers. The question how a real object can be efficiently converted into 3D image data for a computer is an important problem for the structuring of systems, such as for electronic shopping, electronic libraries, etc., recreating objects realistically on a computer screen with 3D computer graphics technology.
The simplest method of generating data of a 3D object for a computer is to capture the 3D object from several directions to generate 2D image data, and to display the captured 2D image taken from the direction that is closest to the direction of the user on a display for reproduction. However, with this method, there is the problem that images of the 3D object from directions other than the directions from which the object has been captured cannot be displayed. Moreover, the images are 2D images after all, so that it is difficult to combine them with images of other 3D objects generated as 3D computer graphics data. To make it possible to display a captured 3D object from any direction, it is important to restore a 3D shape of the object as 3D image data, based on the 2D image data capturing the object from a plurality of directions, so that a projection image of the 3D shape can be generated and displayed for any direction.
Several methods have been proposed for restoring the 3D shape of an object as 3D image data from captured 2D image data. A prominent example is the method based on feature points. The generation of 3D image data with this method includes the following operations, illustrated by the flowchart in FIG. 14. FIG. 15 illustrates the conventional principle of 3D image data generation based on feature points.
First of all, a captured image is read in, from which feature points are derived (operation 1401). For the derivation of these feature points, it is preferable that points where the brightness of the captured 2D image changes are selected as feature points. The feature points can be derived automatically by a computer searching for brightness changes, or they can be specified by hand. An example of a derivation of feature points is shown in FIG. 15. In this example, the four feature points shown in FIG. 15B are derived from the captured image in FIG. 15A.
Then, the correspondence of the derived feature points among the captured images is established (operation 1402). If the positional relation between the captured images, similarities among the images, and the positional relation between the derived feature points are utilized for establishing the correspondence among the feature points, operation 1402 can be processed automatically with a computer. Of course, the feature points also can be specified by hand. In the example in FIG. 15, the correspondence of the feature points 1 to 4 has been established as shown in FIG. 15C.
Then, the 3D coordinates of the feature points are determined by the principle of stereoscopy from the correspondence relation of the feature points (operation 1403), whereby each feature point is expressed as a point in 3D space.
Then, faces are assigned to the feature points arranged in 3D space, and a polyhedron is formed (operation 1404). Here, combinations of feature points defining a face are not arbitrary combinations, but have to be selected so as to form the outer surface of the object to be reproduced. In the example of FIG. 15, the faces are assigned as shown in FIG. 15D, forming a tetrahedron.
Then, textures are generated for the faces (operation 1405). For the generation of textures, it is possible to compute textures referring to the patterns on the captured images, and map them onto the faces.
With these operations S1401 to S1405, 3D image data can be generated from captured images. In the example of FIG. 15, 3D image data can be generated from the original 3D object, as shown in FIG. 15E.
On the other hand, the reproduction of the 3D object on a computer screen, using the generated 3D image data, includes the following operations, illustrated by the flowchart in FIG. 16.
First of all, the position of the user with respect to the object is specified. That is, the direction and distance with respect to the object are specified (operation 1601).
Then, the position of each feature point on a projection plane corresponding to the direction and distance of the specified viewpoint with respect to the object is calculated, and a projection image is obtained (operation 1602). At this stage, texture mapping has not yet been performed.
Then, a texture is mapped on each face of the projection image (operation 1603). For the mapping of the texture, the texture is adjusted calculating the size, shape and direction of each projected face.
Finally, after applying the necessary special effects, such as lighting, tracing and shading, the 3D shape is displayed on a computer screen (operation 1604).
With these operations S1601 to S1605, a 3D object can be displayed from any direction on a computer screen, using the generated 3D image data.
Of the conventional 3D shape generation processing operations, the following methods are known for assigning faces to restore a 3D shape based on the feature point correspondences, shown as operation 1404 in FIG. 14. However, each of these methods poses problems, also described below.
A first conventional method for assigning faces is the projection of 3D feature points onto a surface of a known shape. This method projects the 3D feature points onto a developable surface with a known shape, such as a conical surface or a cylindrical surface, and uses the connections among the vertices, which have been determined before. This processing method is simple and can be regarded as an effective technique.
However, in this first processing method the 3D shape must be already known, or the projection center for the projection towards the developable surface, has to be determined in a manner that there is no pair of faces where the projection overlaps in the projection processing from the center point onto the developable surface. In other words, there is the problem that this method cannot be used for the case where there are complex 3D shapes of unknown shape including dents.
A second conventional method for assigning faces is to determine the direction of the normal on the faces using brightness information, and to assign faces so that this direction is the normal. With irradiation from the direction of a light source during the time of the projection, the brightness at the feature points on the faces of the 3D shape correlate to the direction of the normal of those faces, so that using brightness information, the directions of the normal on the faces at the 3D feature points can be determined, and the faces can be assigned.
However, this second processing method can be used only when the 3D shape is comparatively not complex, and it has no bumps or dents. That is to say, near bumps or dents, the brightness information changes abruptly, so that often the direction of the normal cannot be determined, or a wrong direction is determined for the normal, and there is the problem that this method cannot be used for those cases.
A third conventional method for assigning faces is to display the derived feature points on a display screen, and to specify some of those feature points by hand to determine the faces of the 3D shape. If the user specifies the feature points correctly, the 3D shape can be restored and generated without error.
However, in this third processing method, when the shape is complex and the number of faces and the number of feature points becomes large, the specification by the user becomes arduous, the processing time becomes extremely long, and the processing method is not practicable. Moreover, if the user does not know the 3D shape to be restored, it may be impossible to perform the method just by specifying feature points, and in this case, the specification has to be done while comparing the feature points with a projection image, which makes the operation even more arduous.
In light of the problems of conventional methods for 3D shape generation, it is an object of the present invention to provide a 3D shape generation apparatus that can realize the restoration of 3D shapes based on feature points with high precision and high efficiency, even when there are many feature points and the shape is complex.
A first 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape. This 3D shape generation apparatus comprises:
an input portion for inputting feature point information, capturing direction information, and visibility information, which represents the relation between a capturing direction and feature points that are visible from the capturing direction and appear in the captured image;
a feature point placement portion for placing the feature points in a virtual space, based on the feature point information;
a visible face assigning portion for assigning faces to the feature points that are visible from the capturing direction so that the feature points stay visible, based on the capturing direction information and the visibility information; and
a 3D shape output portion for outputting and displaying a 3D shape that has faces assigned by said visible face assigning portion as its outer surface.
With this configuration, the assigning of faces to feature points can be performed in a simple and suitable manner, satisfying the visibility information of feature points and capturing viewpoints even for complex 3D shapes with bumps and dents. For the procedure of assigning faces satisfying the visibility information, lines passing through feature points toward the capturing directions from which the respective feature points are visible are drawn with respect to faces assigned to feature points that are visible from a capturing direction, when the lines intersect with an assigned faces, then the intersecting face is eliminated, and only the faces with which the drawn lines do not intersect are taken as the output of the visible face assigning portion. Moreover, when the faces of the Delaunay diagram of the feature points are taken as the faces to be assigned, a simple and fast algorithm can be employed. Here, xe2x80x9cDelaunayxe2x80x9d diagram means a set of tetrahedrons into which a convex hull has been partitioned.
A second 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape. This 3D shape generation apparatus comprises:
an input portion for inputting feature point information, capturing direction information, and visibility information, which represents the relation between a capturing direction and feature points that are visible from the capturing direction and appear in the captured image;
a feature point placement portion for placing the feature points in a virtual space, based on the feature point information;
a convex hull solid formation portion for forming a convex hull solid using the feature points;
a sight-obstructing solid part eliminating portion for eliminating parts of the solid that cover feature points that are visible from a capturing direction, based on the capturing direction information and the visibility information; and
a 3D shape output portion for taking the solid remaining after the elimination with said sight-obstructing solid part eliminating portion as the 3D shape and outputting and displaying the 3D shape.
With this configuration, in the procedure for restoring the 3D shape based on feature points, first, a large frame for the 3D shape is formed in a simple and fast manner, using a convex hull of feature points, then, solid portions hiding feature points are eliminated based on the visibility information, whereby the restoration of a detailed shape with dents can be performed, and a 3D shape can be generated with high speed and high precision.
A third 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape. This 3D shape generation apparatus comprises:
an input portion for inputting feature point information, capturing direction information, and masking image information, which represents a capturing direction and a projected shape of an outer perimeter of the 3D shape seen from the capturing direction;
a 3D masking portion, which first generates a solid block aggregation filling a virtual space with basic solid blocks, and, based on the capturing direction information and the masking image information, eliminates basic solid blocks from the solid block aggregation that are outside the perimeter indicated by the masking image information when seen from a capturing direction; and
a 3D shape output portion for outputting the remaining aggregation of basic solid blocks as a 3D shape and displaying the 3D shape.
A fourth 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape. This 3D shape generation apparatus comprises:
an input portion for inputting feature point information, capturing direction information, visibility information which represents the relation between a capturing direction and feature points that are visible from the capturing direction and appear in the captured image, and masking image information which represents a capturing direction and a projected shape expressing an outer perimeter of the 3D shape seen from the capturing direction;
a feature point placement portion for placing the feature points in a virtual space, based on the feature point information;
a 3D masking portion, which first generates a solid block aggregation filling a virtual space with basic solid blocks, and, based on the capturing direction information and the masking image information, eliminates basic solid blocks from the solid block aggregation that are outside the perimeter indicated by the masking image information when seen from a capturing direction;
a sight-obstructing solid part eliminating portion for eliminating basic solid blocks that cover feature points that are visible from a capturing direction, based on the capturing direction information and the visibility information; and
a 3D shape output portion for outputting the remaining aggregation of basic solid blocks remaining after the elimination with said sight-obstructing solid part eliminating portion as a 3D shape and displaying the 3D shape.
With this configuration, in the procedure for restoring the 3D shape based on feature points, a large frame of the outer shape of the 3D shape is formed with an aggregation of basic solid blocks using masking image information, then, solid portions hiding feature points are eliminated based on the visibility information, whereby the restoration of a detailed shape with dents can be performed, and a 3D shape can be generated with high speed and high precision. For the elimination of basic solid blocks with the sight-obstructing solid part eliminating portion, it is preferable that lines are drawn from the capturing direction from which the feature points are visible to the feature points, and if the drawn lines intersect with the aggregation of basic solid blocks, the intersecting basic solid blocks are removed. It is also preferable that the basic solid blocks use tetrahedrons of a Delaunay diagram of the 3D feature points.
A first computer-readable recording medium storing a program for realizing a 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape. This program comprises:
an operation for inputting feature point information, capturing direction information, and visibility information, which represents the relation between a capturing direction and feature points that are visible from the capturing direction and appear in the captured image;
a feature point placement for placing the feature points in a virtual space, based on the feature point information;
a visible face assigning operation for assigning faces to the feature points that are visible from the capturing direction so that the feature points stay visible, based on the capturing direction information and the visibility information; and
a 3D shape output operation for outputting and displaying a 3D shape that has the faces assigned in the visible face assigning operation as its outer surface.
A second computer-readable recording medium storing a program for realizing a 3D shape generation apparatus in accordance with the present invention restores and generates a 3D shape on a computer screen, based on data of feature points derived from a 3D shape and 2D image data of an outer surface of the 3D shape, the program comprising:
an operation for inputting feature point information, capturing direction information, and masking image information, which represents a capturing direction and a projected shape expressing an outer perimeter of the 3D shape seen from each capturing direction;
a 3D masking operation, which first generates a solid block aggregation filling a virtual space with basic solid blocks, and, based on the capturing direction information and the masking image information, eliminates basic solid blocks from the solid block aggregation that are outside the perimeter indicated by the masking image information when seen from each capturing direction; and
a 3D shape output operation for outputting the remaining aggregation of basic solid blocks remaining after the elimination in the sight-obstructing solid portion eliminating operation as a 3D shape and displaying the 3D shape.
By reading such a program into a computer, a fast 3D shape generation apparatus with high restoration precision using visibility information of feature points of 3D shapes and capturing viewpoints can be implemented on the computer.